/*
 This source file is part of the Swift.org open source project

 Copyright (c) 2021-2025 Apple Inc. and the Swift project authors
 Licensed under Apache License v2.0 with Runtime Library Exception

 See https://swift.org/LICENSE.txt for license information
 See https://swift.org/CONTRIBUTORS.txt for Swift project authors
*/

public import Foundation
import Crypto

/**
 A `NavigatorIndex` contains all the necessary information to display the data inside a navigator.
 The data ranges from the tree to the necessary pieces of information to filter the content and perform actions in a fast way.
 A navigator index is created per bundle and needs a bundle identifier to correctly work. Anonymous bundles are allowed, but they limit
 the functionalities of the index.
 
 A `NavigatorIndex` is composed by two main components:
    - A navigator tree reflecting the content curation
    - An availability index storing the information about for which platform and SDK a given symbol is available and they map USR to document's path
 
 The two mentioned components are generated by using a `NavigatorIndex.Builder` instance, which indexes the content accordingly to the desired configuration.
 A `NavigatorIndex` can be stored on disk to be later loaded. Loading an index can be performed in a single operation (synchronous) or asynchronously.
 This option is extremely useful in case an application needs to load a very large amount of data while updating the UI to let the user navigate the loaded content,
 while the remaining is loaded in a background thread and presented later in time.
 
 There are few important pieces information a `NavigatorIndex` requires to properly work:
    - A bundle identifier
    - A valid LMDB database for storing availability information
    - A valid navigator tree
 
 Building an index with one of the mentioned components is not supported.
 */
public class NavigatorIndex {
    
    /// A string indicating an unknown bundle identifier.
    public static let UnknownBundleIdentifier = ""
    
    /// The key used to store the name of the bundle inside the database.
    public static let bundleKey = "bundleIdentifier"
    
    /// The key used to store the name of path hasher inside the database.
    public static let pathHasherKey = "pathHasher"
    
    /// The key used to store the number of indexed items.
    public static let itemsIndexKey = "itemsIndex"
    
    /// A specific error to describe issues when processing a `NavigatorIndex`.
    public enum Error: Swift.Error, DescribedError {
        
        /// Missing bundle identifier.
        case missingBundleIdentifier
        
        /// A RenderNode has no title and won't be indexed.
        case missingTitle(description: String)
        
        /// The navigator index has not been initialized.
        case navigatorIndexIsNil
        
        public var errorDescription: String {
            switch self {
            case .missingBundleIdentifier:
                return "A navigator index requires a bundle identifier, which is missing."
            case .missingTitle:
                return "The page has no valid title available."
            case .navigatorIndexIsNil:
                return "The NavigatorIndex is Nil and can't be processed."
            }
        }
    }
    
    /// The url of the index.
    public let url: URL
    
    /// The LMDB environment.
    var environment: LMDB.Environment?
    
    /// The path hasher.
    ///
    /// The hasher is used to make paths, like "/documentation/mykit/myclass/mysymbol", shorter for storage inside the LMDB database,
    /// avoiding storing very long strings, multiple times that will cause an index to use unnecessary space on disk.
    var pathHasher: PathHasher = .md5
    
    /// The index database in LMDB.
    private var database: LMDB.Database?
    
    /// The information dedicated database to store data such as the bundle identifier or the number of items indexed.
    private var information: LMDB.Database?
    
    /// The availability dedicated database.
    private var availability: LMDB.Database?
    
    /// The navigator tree.
    public let navigatorTree: NavigatorTree
    
    /// The availability index.
    public let availabilityIndex: AvailabilityIndex
    
    /// Bundle Identifier.
    public var bundleIdentifier: String = NavigatorIndex.UnknownBundleIdentifier
    
    /// A presentation identifier used to disambiguate content in presentation contexts.
    public let presentationIdentifier: String?
    
    /// The available languages in the index.
    public lazy var languages: [String] = {
        return self.availabilityIndex.interfaceLanguages.map{ $0.name }
    }()
    
    /// The mapping from a single language mask to its interface language type.
    public lazy var languageMaskToLanguage: [UInt8: InterfaceLanguage] = {
        var value = [UInt8: InterfaceLanguage]()
        for language in Array(availabilityIndex.interfaceLanguages) {
            value[language.mask] = language
        }
        return value
    }()
    
    /// The number of item indexed.
    public lazy var count: Int = {
        return self.information?.get(type: Int.self, forKey: NavigatorIndex.itemsIndexKey) ?? 0
    }()
    
    /**
     Initializes a `NavigatorIndex` from a given path on disk.
     
     Most uses should be made using just the url parameter:
     ```swift
    let indexFilePath = URL(string: "file://path/to/index/on/disk")
    let index = NavigatorIndex.readNavigatorIndex(url: indexFilePath)
     ```
     
     - Parameters:
        - url: The URL pointing to the path from which the index should be read.
        - bundleIdentifier: The name of the bundle the index is referring to.
        - readNavigatorTree: Indicates if the init the navigator tree should be read from the disk now or later, if false, then `readNavigatorTree` needs to be called later. Default: `true`.
        - presentationIdentifier: Indicates if the index has an identifier useful for presentation contexts.
        - onNodeRead: An action to perform after reading a node. This allows clients to perform arbitrary actions on the node while it is being read from disk. This is useful for clients wanting to attach data to ``NavigatorTree/Node/attributes``.
     
     - Throws: A `NavigatorIndex.Error` describing the nature of the problem.
     
     - Note: The index powered by LMDB opens in `readOnly` mode to avoid performing a filesystem lock which fails without writing permissions. As this initializer opens a built index, write permission is not expected.
     */
    public static func readNavigatorIndex(
        url: URL,
        bundleIdentifier: String? = nil,
        readNavigatorTree: Bool = true,
        presentationIdentifier: String? = nil,
        onNodeRead: ((NavigatorTree.Node) -> Void)? = nil
    ) throws -> NavigatorIndex {
        // To avoid performing a filesystem lock which might fail without write permission, we pass `.readOnly` and `.noLock` to open the index.
        let environment = try LMDB.Environment(path: url.path, flags: [.readOnly, .noLock], maxDBs: 4, mapSize: 100 * 1024 * 1024) // mapSize = 100MB
        let database = try environment.openDatabase(named: "index", flags: [])
        let availability = try environment.openDatabase(named: "availability", flags: [])
        
        let information = try environment.openDatabase(named: "information", flags: [])
        
        let data = try Data(contentsOf: url.appendingPathComponent("availability.index", isDirectory: false))
        let plistDecoder = PropertyListDecoder()
        let availabilityIndex = try plistDecoder.decode(AvailabilityIndex.self, from: data)
        let bundleIdentifier = bundleIdentifier ?? information.get(type: String.self, forKey: NavigatorIndex.bundleKey) ?? NavigatorIndex.UnknownBundleIdentifier
        
        guard bundleIdentifier != NavigatorIndex.UnknownBundleIdentifier else {
            throw Error.missingBundleIdentifier
        }
        
        // Use `.fnv1` by default if no path hasher is set for compatibility reasons.
        let pathHasher = PathHasher(rawValue: information.get(type: String.self, forKey: NavigatorIndex.pathHasherKey) ?? "") ?? .fnv1
        
        let navigatorTree: NavigatorTree
        if readNavigatorTree {
            navigatorTree = try NavigatorTree.read(
                from: url.appendingPathComponent("navigator.index", isDirectory: false),
                bundleIdentifier: bundleIdentifier,
                presentationIdentifier: presentationIdentifier,
                onNodeRead: onNodeRead)
        } else {
            navigatorTree = NavigatorTree()
        }
        
        return NavigatorIndex(
            url: url,
            presentationIdentifier: presentationIdentifier,
            bundleIdentifier: bundleIdentifier,
            environment: environment,
            database: database,
            availability: availability,
            information: information,
            availabilityIndex: availabilityIndex,
            pathHasher: pathHasher,
            navigatorTree: navigatorTree
        )
    }
    
    fileprivate init(
        url: URL,
        presentationIdentifier: String?,
        bundleIdentifier: String,
        environment: LMDB.Environment,
        database: LMDB.Database,
        availability: LMDB.Database,
        information: LMDB.Database,
        availabilityIndex: AvailabilityIndex,
        pathHasher: PathHasher,
        navigatorTree: NavigatorTree
    ) {
        self.url = url
        self.presentationIdentifier = presentationIdentifier
        self.bundleIdentifier = bundleIdentifier
        self.environment = environment
        self.database = database
        self.availability = availability
        self.information = information
        self.availabilityIndex = availabilityIndex
        self.pathHasher = pathHasher
        self.navigatorTree = navigatorTree
    }
    
    /**
     Initialize a `NavigatorIndex` from a given path with an empty tree.
     
     - Parameter url: The URL pointing to the path from which the index should be read.
     - Parameter bundleIdentifier: The name of the bundle the index is referring to.
     
     - Note: Don't expose this initializer as it's used **ONLY** for building an index.
     */
    fileprivate init(withEmptyTree url: URL, bundleIdentifier: String) throws {
        self.url = url
        self.bundleIdentifier = bundleIdentifier
        self.presentationIdentifier = nil
        self.navigatorTree = NavigatorTree(root: NavigatorTree.rootNode(bundleIdentifier: bundleIdentifier))
        self.availabilityIndex = AvailabilityIndex()
        
        guard self.bundleIdentifier != NavigatorIndex.UnknownBundleIdentifier else {
            throw Error.missingBundleIdentifier
        }
    }
    
    /// Indicates the page type of a given item inside the tree.
    /// - Note: This information is stored as `UInt8` to decrease the required size to store it and make the comparison faster between types.
    public enum PageType: UInt8 {
        case root = 0
        case article = 1
        case tutorial = 2
        case section = 3
        case learn = 4
        case overview = 5
        case resources = 6
        case symbol = 7 // This indicates a generic symbol
        
        // Symbol specialization
        case framework = 10
        case `class` = 20
        case structure = 21
        case `protocol` = 22
        case enumeration = 23
        case function = 24
        case `extension` = 25
        case localVariable = 26
        case globalVariable = 27
        case typeAlias = 28
        case associatedType = 29
        case `operator` = 30
        case macro = 31
        case union = 32
        case enumerationCase = 33
        case initializer = 34
        case instanceMethod = 35
        case instanceProperty = 36
        case instanceVariable = 37
        case `subscript` = 38
        case typeMethod =  39
        case typeProperty = 40
    
        // Data entities:
        case buildSetting = 42
        case propertyListKey = 43

        // Other:
        case sampleCode = 44

        // REST entities:
        case httpRequest = 45
        case dictionarySymbol = 46

        // A property list key.
        case propertyListKeyReference = 47

        // C++ symbols
        case namespace = 48
        
        // Special items
        case languageGroup = 127
        case container = 254
        case groupMarker = 255 // UInt8.max
                
        /// Initialize a page type from a `role` and a `symbolKind` returning the Symbol type.
        init(symbolKind: String) {
            // Prioritize the SymbolKind first
            switch symbolKind.lowercased() {
            case "module": self = .framework
            case "cl", "class": self = .class
            case "struct", "tag": self = .structure
            case "intf", "protocol": self = .protocol
            case "enum": self = .enumeration
            case "func", "function": self = .function
            case "extension": self = .extension
            case "data", "var": self = .globalVariable
            case "tdef", "typealias": self = .typeAlias
            case "intftdef", "associatedtype": self = .associatedType
            case "op", "opfunc", "intfopfunc", "func.op": self = .operator
            case "macro": self = .macro
            case "union": self = .union
            case "enumelt", "econst", "enum.case", "case": self = .enumerationCase
            case "enumctr", "structctr", "instctr", "intfctr", "constructor", "initializer", "init": self = .initializer
            case "enumm", "structm", "instm", "intfm", "method": self = .instanceMethod
            case "enump", "structp", "instp", "intfp", "unionp", "pseudo", "variable", "property": self = .instanceProperty
            case "enumdata", "structdata", "cldata", "clconst", "intfdata", "type.property", "typeConstant": self = .instanceVariable
            case "enumsub", "structsub", "instsub", "intfsub", "subscript": self = .subscript
            case "enumcm", "structcm", "clm", "intfcm", "type.method": self = .typeMethod
            case "httpget", "httpput", "httppost", "httppatch", "httpdelete": self = .httpRequest
            case "dict": self = .dictionarySymbol
            case "namespace": self = .namespace
            default: self = .symbol
            }
        }
        
        init(role: String) {
            switch role.lowercased() {
            case "symbol", "containersymbol": self = .symbol
            case "restrequestsymbol": self = .httpRequest
            case "dictionarysymbol": self = .dictionarySymbol
            case "pseudosymbol": self = .symbol
            case "pseudocollection": self = .framework
            case "collection": self = .framework
            case "collectiongroup": self = .symbol
            case "article": self = .article
            case "samplecode": self = .sampleCode
            default: self = .article
            }
        }

        /// Whether this page kind references a symbol.
        var isSymbolKind: Bool {
            switch self {
            case .root, .article, .tutorial, .section, .learn, .overview, .resources, .framework,
                    .buildSetting, .sampleCode, .languageGroup, .container, .groupMarker:
                return false
            case .symbol, .class, .structure, .protocol, .enumeration, .function, .extension,
                    .localVariable, .globalVariable, .typeAlias, .associatedType, .operator, .macro,
                    .union, .enumerationCase, .initializer, .instanceMethod, .instanceProperty,
                    .instanceVariable, .subscript, .typeMethod, .typeProperty, .propertyListKey,
                    .httpRequest, .dictionarySymbol, .propertyListKeyReference, .namespace:
                return true
            }
        }
    }
    
    // MARK: - Read Navigator Tree
    
    /**
    Read a tree on disk from a given path.
    The read is atomically performed, which means it reads all the content of the file from the disk and process the tree from loaded data.
    The queue is used to load the data for a given timeout period, after that, the queue is used to schedule another read after a given delay.
    This approach ensures that the used queue doesn't stall while loading the content from the disk keeping the used queue responsive.
    
    - Parameters:
       - timeout: The duration for which we can load a batch of items from data. Once the timeout duration passes,
                  the reading process will reschedule asynchronously using the given queue.
       - delay: The duration to wait for before scheduling the next read. Default: 0.01 seconds.
       - queue: The queue to use.
       - broadcast: The callback to receive updates on the status of the current process.
     
    - Note: Do not access the navigator tree root node or the map from identifier to node from a different thread than the one the queue is using while the read is performed,
     this may cause data inconsistencies. For that please use the broadcast callback that notifies which items have been loaded.
    */
    public func readNavigatorTree(timeout: TimeInterval, delay: TimeInterval = 0.01, queue: DispatchQueue, broadcast: NavigatorTree.BroadcastCallback?) throws {
        let indexURL = url.appendingPathComponent("navigator.index")
        try navigatorTree.read(from: indexURL, bundleIdentifier: bundleIdentifier, timeout: timeout, delay: delay, queue: queue, broadcast: broadcast)
    }
    
    // MARK: - Data Query
    
    /// Returns an array of availabilities based on a single id.
    public func availabilities(for id: UInt64) -> [AvailabilityIndex.Info] {
        let array = availability?.get(type: [Int].self, forKey: id)
        return array?.compactMap{ availabilityIndex.info(for: $0) } ?? []
    }
    
    /// Returns the path of a given USR if existing.
    /// - Parameters:
    ///   - usr: The full USR or a hashed USR.
    ///   - language: The interface language to look the USR for.
    ///   - hashed: A boolean indicating if the USR is hashed or not.
    /// - Returns: The path of a given USR, if available.
    public func path(for usr: String, language: InterfaceLanguage = .swift, hashed: Bool = false) -> String? {
        let usrKey = language.name + "-" + ((hashed) ? usr : ExternalIdentifier.usr(usr).hash)
        guard let nodeID = database?.get(type: UInt32.self, forKey: usrKey) else { return nil }
        return path(for: nodeID)
    }
    
    /// If available, returns the path from the numeric ID inside the navigator tree.
    public func path(for id: UInt32) -> String? {
        guard var path = database?.get(type: String.self, forKey: id) else { return nil }
        // Remove the language prefix.
        if let slashRange = path.range(of: "/") {
            path.removeSubrange(path.startIndex..<slashRange.lowerBound)
        }
        return path
    }
    
    /// If available, returns the ID of a path for the given language.
    public func id(for path: String, with interfaceLanguage: InterfaceLanguage) -> UInt32? {
        // The fullPath needs to account for the language.
        let fullPath = interfaceLanguage.name.lowercased() + path
        return database?.get(type: UInt32.self, forKey: pathHasher.hash(fullPath))
    }
}

extension ResolvedTopicReference {
    func normalizedNavigatorIndexIdentifier(
        forLanguage languageIdentifier: InterfaceLanguage.ID
    ) -> NavigatorIndex.Identifier {
        let normalizedPath = NodeURLGenerator.fileSafeReferencePath(self, lowercased: true)
        
        return NavigatorIndex.Identifier(
            bundleIdentifier: bundleID.rawValue.lowercased(),
            path: "/" + normalizedPath,
            fragment: fragment,
            languageIdentifier: languageIdentifier
        )
    }
}

extension NavigatorIndex {
    /// A unique identifier for navigator index items.
    ///
    /// Used to identify relationships in the navigator index during the index build process.
    public struct Identifier: Hashable {
        let bundleIdentifier: String
        let path: String
        let fragment: String?
        let languageIdentifier: InterfaceLanguage.ID
        
        init(
            bundleIdentifier: String,
            path: String,
            fragment: String? = nil,
            languageIdentifier: InterfaceLanguage.ID
        ) {
            self.bundleIdentifier = bundleIdentifier
            self.path = path
            self.fragment = fragment
            self.languageIdentifier = languageIdentifier
        }

        /// Compare an identifier with another one, ignoring the identifier language.
        ///
        /// Used when curating cross-language references in multi-language frameworks.
        ///
        /// - Parameter other: The other identifier to compare with.
        func isEquivalentIgnoringLanguage(to other: Identifier) -> Bool {
            return self.bundleIdentifier == other.bundleIdentifier &&
                   self.path == other.path &&
                   self.fragment == other.fragment
        }
    }
    
    /**
     A `Builder` is a utility class to build a navigator index.
     
     The builder generates an index for content navigation, but also maps important information to filter content based on availability, symbol type, platform and some others.
     
     - Note: The builder is not thread safe and therefore, calling `index(renderNode:)` requires external synchronization in case the process is performed on different threads.
     */
    open class Builder {
        
        /// The documentation archive to build an index from.
        public let archiveURL: URL?
        
        /// The output URL.
        public let outputURL: URL
        
        /// The bundle name.
        public let bundleIdentifier: String
        
        /// Indicates if the root children must be sorted by title.
        public let sortRootChildrenByName: Bool
        
        /// Indicates if the children need to be grouped by languages.
        public let groupByLanguage: Bool
        
        /// The navigator index.
        public private(set) var navigatorIndex: NavigatorIndex?
        
        /// An array holding all problems encountered during the index build.
        public private(set) var problems = [Problem]()
        
        /// The number of items processed during a build.
        public private(set) var counter = 0
        
        /// Indicates if a building process has been completed.
        public private(set) var isCompleted = false
        
        /// The map of identifier to navigation item.
        private var identifierToNode = [Identifier: NavigatorTree.Node]()
        
        /// The map of identifier to children.
        private var identifierToChildren = [Identifier: [Identifier]]()
        
        /// A temporary list of pending references that are waiting for their parent to be indexed.
        private var pendingUncuratedReferences = Set<Identifier>()
        
        /// A map with all nodes that are curated multiple times in the tree and need to be processed at the very end.
        private var multiCurated = [Identifier: NavigatorTree.Node]()
        
        /// A set with all nodes that are curated multiple times, but still have to be visited.
        private var multiCuratedUnvisited = Set<Identifier>()
        
        /// A set with all nodes that are curated.
        private var curatedIdentifiers = Set<Identifier>()
        
        /// Maps an arbitrary InterfaceLanguage string to an InterfaceLanguage.
        private var idToLanguage = [String: InterfaceLanguage]()
        
        /// Maps an arbitrary Platform name string to a Platform.Name instance.
        private var nameToPlatform = [String: Platform.Name]()
        
        // availabilityIDs and availabilityToID serve as a bidirectional map to lookup entries in the
        // availabilityIndex of the NavigatorIndex. NavigatorItem stores an availabilityID that corresponds
        // to the key of availabilityIDs. The associated value for that availabilityID corresponds
        // to a list of IDs which is used to get the availability information from the availability index.
        // availabilityToID is used to reuse the same availabilityID if two NavigatorItem have the same
        // availability information.
        
        private static let availabilityIDWithNoAvailabilities = 0
        
        /// The map of the availabilities from a single availabilityID to an array of availabilities inside the availability index.
        /// This approach gives us the opportunity to map multiple availabilities with the same entries using a single ID.
        /// Ex. An item with: iOS 13.0 and macOS 10.15 can share the same ID with other items having exactly the same availability.
        /// We use the `0` value to indicate that there are no associated availabilityIndex entries.
        private var availabilityIDs: [Int: [Int]] = [availabilityIDWithNoAvailabilities: []]
        
        /// The map of the availabilities to their ID, the opposite of `availabilityIDs`.
        /// Conversely we make sure that an empty list of IDs into the availabilityIndex maps back to the `0` value.
        private var availabilityToID: [[Int]: Int] = [[]: availabilityIDWithNoAvailabilities]
        
        /// Indicates if the path component inside the navigator item needs to be persisted or not.
        private let writePathsOnDisk: Bool
        
        /// Indicates if the page title should be used instead of the navigator title.
        private let usePageTitle: Bool
        
        /// Maps the icon render references in the navigator items created by this builder
        /// to their image references.
        ///
        /// Use the `NavigatorItem.icon` render reference to look up the full image reference
        /// for any custom icons used in this navigator index.
        var iconReferences = [String : ImageReference]()
        
        /// Create a new a builder with the given data provider and output URL.
        /// - Parameters:
        ///    - archiveURL: The location of the documentation archive that the builder builds an navigator index for.
        ///    - outputURL: The location where the builder will write the the built navigator index.
        ///    - bundleIdentifier: The bundle identifier of the documentation that the builder builds a navigator index for.
        ///    - sortRootChildrenByName: Configure the builder to sort root's children by name.
        ///    - groupByLanguage: Configure the builder to group the entries by language.
        ///    - writePathsOnDisk: Configure the builder to write each navigator item's path components to the location.
        ///    - usePageTitle: Configure the builder to use the "page title" instead of the "navigator title" as the title for each entry.
        public init(archiveURL: URL? = nil, outputURL: URL, bundleIdentifier: String, sortRootChildrenByName: Bool = false, groupByLanguage: Bool = false, writePathsOnDisk: Bool = true, usePageTitle: Bool = false) {
            self.archiveURL = archiveURL
            self.outputURL = outputURL
            self.bundleIdentifier = bundleIdentifier
            self.sortRootChildrenByName = sortRootChildrenByName
            self.groupByLanguage = groupByLanguage
            self.writePathsOnDisk = writePathsOnDisk
            self.usePageTitle = usePageTitle
        }
        
        /// Setup the builder to process render nodes.
        public func setup() {
            // If setup has been called already, skip.
            guard navigatorIndex == nil && isCompleted == false else { return }
            
            do {
                // The folder in which the environment, if existing, will be overwritten.
                if FileManager.default.fileExists(atPath: outputURL.path) {
                    try FileManager.default.removeItem(at: outputURL)
                }
                try FileManager.default.createDirectory(at: outputURL, withIntermediateDirectories: true, attributes: nil)
                
                navigatorIndex = try NavigatorIndex(withEmptyTree: outputURL, bundleIdentifier: bundleIdentifier)
            } catch {
                problems.append(error.problem(source: outputURL,
                                              severity: .error,
                                              summaryPrefix: "The folder couldn't be processed correctly."))
            }
            
            // Setup the default known values for Platforms and Languages
            for language in InterfaceLanguage.apple {
                idToLanguage[language.id.lowercased()] = language
            }
            
            for platformName in Platform.Name.apple {
                nameToPlatform[platformName.name.lowercased()] = platformName
            }
        }
        
        /// Index a single render `ExternalRenderNode`.
        /// - Parameter renderNode: The render node to be indexed.
        package func index(renderNode: ExternalRenderNode, ignoringLanguage: Bool = false) throws {
            let navigatorRenderNode = NavigatorExternalRenderNode(renderNode: renderNode)
            _ = try index(navigatorRenderNode, traits: nil, isExternal: true)
            guard renderNode.identifier.sourceLanguage != .objectiveC else {
                return
            }
            // Check if the render node has an Objective-C representation
            guard let objCVariantTrait = renderNode.variants?.flatMap(\.traits).first(where: { trait in
                switch trait {
                case .interfaceLanguage(let language):
                    return InterfaceLanguage.from(string: language) == .objc
                }
            }) else {
                return
            }
            // If this external render node has a variant, we create a "view" into its Objective-C specific data and index that.
            let objVariantView = NavigatorExternalRenderNode(renderNode: renderNode, trait: objCVariantTrait)
            _ = try index(objVariantView, traits: [objCVariantTrait], isExternal: true)
        }
        
        /// Index a single render `RenderNode`.
        /// - Parameter renderNode: The render node to be indexed.
        /// - Parameter ignoringLanguage: Whether language variants should be ignored when indexing this render node.
        public func index(renderNode: RenderNode, ignoringLanguage: Bool = false) throws {
            // Always index the main render node representation
            let language = try index(renderNode, traits: nil)
            
            // Additionally, for Swift want to also index the Objective-C variant, if there is any.
            guard !ignoringLanguage && language == .swift else {
                return
            }
            
            // Check if the render node has an Objective-C representation
            guard let objCVariantTrait = renderNode.variants?.flatMap(\.traits).first(where: { trait in
                switch trait {
                case .interfaceLanguage(let language):
                    return InterfaceLanguage.from(string: language) == .objc
                }
            }) else {
                return
            }
            
            // A render node is structured differently depending on if it was created by "rendering" a documentation node 
            // or if it was deserialized from a documentation archive.
            //
            // If it was created by rendering a documentation node, all variant information is stored in each individual variant collection and the variant overrides are nil.
            // If it was deserialized from a documentation archive, all variant information is stored in the variant overrides and the variant collections are empty.
            
            // Operating on the variant override is _significantly_ slower, so we only take that code path if we have to.
            // The only reason why this code path still exists is to support the `docc process-archive index` command, which creates an navigation index from an already build documentation archive.
            if let overrides = renderNode.variantOverrides, !overrides.isEmpty {
                // This code looks peculiar and very inefficient because it is.
                // I didn't write it and I really wanted to remove it, but it's the only way to support the `docc process-archive index` command for now.
                // rdar://128050800 Tracks fixing the inefficiencies with this code, to make `docc process-archive index` command as fast as indexing during a `docc convert` command.
                //
                // First, it encodes the render node, which was read from a file, back to data; because that's what the overrides applier operates on
                let encodedRenderNode = try renderNode.encodeToJSON()
                // Second, the overrides applier will decode that data into an abstract JSON representation of arrays, dictionaries, string, numbers, etc.
                // After that the overrides applier loops over all the JSON patches and applies them to the abstract JSON representation.
                // With all the patches applies, the overrides applier encodes the abstract JSON representation into data again and returns it.
                let transformedData = try RenderNodeVariantOverridesApplier().applyVariantOverrides(in: encodedRenderNode, for: [objCVariantTrait])
                // Third, this code decodes the render node from the transformed data. If you count reading the render node from the documentation archive, 
                // this is the fifth time that the same node is either encoded or decoded.
                let variantRenderNode = try RenderNode.decode(fromJSON: transformedData)
                // Finally, the decoded node is in a way flattened, so that it only contains its Objective-C content. That's why we pass `nil` instead of `[objCVariantTrait]` to this call.
                _ = try index(variantRenderNode, traits: nil)
            }
            
            // If this render node was created by rendering a documentation node, we create a "view" into its Objective-C specific data and index that.
            let objVariantView = RenderNodeVariantView(wrapped: renderNode, traits: [objCVariantTrait])
            _ = try index(objVariantView, traits: [objCVariantTrait])
        }
        
        // The private index implementation which indexes a given render node representation
        private func index(_ renderNode: any NavigatorIndexableRenderNodeRepresentation, traits: [RenderNode.Variant.Trait]?, isExternal external: Bool = false) throws -> InterfaceLanguage? {
            guard let navigatorIndex else {
                throw Error.navigatorIndexIsNil
            }
            
            // Process the language
            let interfaceLanguage = renderNode.identifier.sourceLanguage
            let interfaceLanguageID = interfaceLanguage.id.lowercased()
            
            let language: InterfaceLanguage
            if InterfaceLanguage.from(string: interfaceLanguageID) != .undefined {
                language = InterfaceLanguage.from(string: interfaceLanguageID)
            } else if let storedLanguage = idToLanguage[interfaceLanguageID] {
                language = storedLanguage
            } else {
                // It's a new language, create a new instance.
                language = InterfaceLanguage(interfaceLanguage.name, id: interfaceLanguage.id, mask: idToLanguage.count)
                idToLanguage[interfaceLanguageID] = language
            }

            let normalizedIdentifier = renderNode
                .identifier
                .normalizedNavigatorIndexIdentifier(forLanguage: language.mask)
            
            guard identifierToNode[normalizedIdentifier] == nil else {
                return nil // skip as item exists already.
            }
            
            guard let title = usePageTitle ? renderNode.metadata.title : renderNode.navigatorTitle() else {
                throw Error.missingTitle(description: "\(renderNode.identifier.absoluteString.singleQuoted) has an empty title and so can't have a usable entry in the index.")
            }
            
            // Get the identifier path
            let identifierPath = normalizedIdentifier.path
            
            // Store the language inside the availability index.
            navigatorIndex.availabilityIndex.add(language: language)
            
            // Process the availability and platform ID
            var platformID: Platform.Name.ID = 0
            var availabilityID: Int = 0
            
            if let platforms = renderNode.metadata.platforms {
                var entryIDs = [Int]()
                for availability in platforms {
                    if let name = availability.name {
                        let platformName: Platform.Name
                        if let existing = nameToPlatform[name.lowercased()] {
                            platformName = existing
                        } else { // Create a new one if non existing.
                            platformName = Platform.Name(name, id: nameToPlatform.count)
                            nameToPlatform[name.lowercased()] = platformName
                        }
                        if language != .undefined {
                            navigatorIndex.availabilityIndex.add(platform: platformName, for: language)
                        }
                        let introduced = Platform.Version(string: availability.introduced ?? "")
                        let deprecated = Platform.Version(string: availability.deprecated ?? "")
                        let info = AvailabilityIndex.Info(platformName: platformName, introduced: introduced, deprecated: deprecated)
                        
                        // Append a single availability ID
                        if let id = navigatorIndex.availabilityIndex.id(for: info, createIfMissing: true) {
                            entryIDs.append(id)
                        }
                        
                        // Add the mask to the platform ID
                        platformID += platformName.mask
                    }
                }
                
                // Sort the IDs so multiple entries with the same availabilities
                // will generate the same hash. In this way we can find them in the dictionary.
                entryIDs.sort()
                
                if let existing = availabilityToID[entryIDs] {
                    availabilityID = existing
                } else {
                    let newID = availabilityIDs.count
                    availabilityToID[entryIDs] = newID
                    availabilityIDs[newID] = entryIDs
                    availabilityID = newID
                }
            }
            
            
            if let icon = renderNode.icon,
                let iconRenderReference = renderNode.references[icon.identifier] as? ImageReference
            {
                iconReferences[icon.identifier] = iconRenderReference
            }
            
            let navigationItem = NavigatorItem(
                pageType: renderNode.navigatorPageType().rawValue,
                languageID: language.mask,
                title: title,
                platformMask: platformID,
                availabilityID: UInt64(availabilityID),
                icon: renderNode.icon,
                isExternal: external,
                isBeta: renderNode.metadata.isBeta
            )
            navigationItem.path = identifierPath
            
            // Index the USR for the given identifier
            if let usr = renderNode.metadata.externalID {
                navigationItem.usrIdentifier =  language.name + "-" + ExternalIdentifier.usr(usr).hash // We pair the hash and the language name
            }
            
            let navigatorNode = NavigatorTree.Node(item: navigationItem, bundleIdentifier: bundleIdentifier)
            
            // Process the children
            var children = [Identifier]()
            for (index, child) in renderNode.navigatorChildren(for: traits).enumerated() {
                let groupIdentifier: Identifier?
                
                if let title = child.name {
                    let fragment = "\(title)#\(index)".addingPercentEncoding(withAllowedCharacters: .urlPathAllowed)!
                    
                    let identifier = Identifier(
                        bundleIdentifier: normalizedIdentifier.bundleIdentifier,
                        path: identifierPath,
                        fragment: fragment,
                        languageIdentifier: language.mask
                    )
                    
                    let groupItem = NavigatorItem(
                        pageType: UInt8(PageType.groupMarker.rawValue),
                        languageID: language.mask,
                        title: title,
                        platformMask: platformID,
                        availabilityID: UInt64(Self.availabilityIDWithNoAvailabilities),
                        isExternal: external
                    )
                    
                    groupItem.path = identifier.path + "#" + fragment
                    
                    let navigatorGroup = NavigatorTree.Node(item: groupItem, bundleIdentifier: bundleIdentifier)
                    
                    identifierToNode[identifier] = navigatorGroup
                    children.append(identifier)
                    
                    groupIdentifier = identifier
                } else {
                    groupIdentifier = nil
                }
                
                let identifiers = child.references.map { reference in
                    return Identifier(
                        bundleIdentifier: bundleIdentifier.lowercased(),
                        path: reference.url.lowercased(),
                        languageIdentifier: language.mask
                    )
                }
                
                var nestedChildren = [Identifier]()
                for identifier in identifiers {
                    if child.referencesAreNested {
                        nestedChildren.append(identifier)
                    } else {
                        children.append(identifier)
                    }
                    
                    // If a topic has been already curated and has a valid node processed, flag it as multi-curated.
                    if curatedIdentifiers.contains(identifier) && pendingUncuratedReferences.contains(identifier) {
                        multiCurated[identifier] = identifierToNode[identifier]
                    } else if curatedIdentifiers.contains(identifier) { // In case we have no node, then keep track.
                        multiCuratedUnvisited.insert(identifier)
                    } else { // Otherwise keep track for later.
                        curatedIdentifiers.insert(identifier)
                    }
                }
                
                if let groupIdentifier, !nestedChildren.isEmpty {
                    identifierToChildren[groupIdentifier] = nestedChildren
                }
            }
            
            // Keep track of the node
            identifierToNode[normalizedIdentifier] = navigatorNode
            identifierToChildren[normalizedIdentifier] = children
            pendingUncuratedReferences.insert(normalizedIdentifier)
            
            // Track a multiple curated node
            if multiCuratedUnvisited.remove(normalizedIdentifier) != nil {
                multiCurated[normalizedIdentifier] = navigatorNode
            }
            
            // Bump the nodes counter.
            counter += 1
            
            return language
        }
        
        /// An internal struct to store data about a single navigator entry.
        struct Record {
            let nodeMapping: (UInt32, String)
            let curationMapping: (String, UInt32)
            let usrMapping: (String, UInt32)?
        }
        
        /// Finalize the process by writing the content on disk.
        ///
        /// By default this function writes out the navigator index to disk as an LMDB database
        /// but emitting a JSON representation of the index is also supported.
        ///
        /// - Parameters:
        ///   - estimatedCount: An estimate of the number of nodes in the navigator index.
        ///
        ///   - emitJSONRepresentation: Whether or not a JSON representation of the index should
        ///     be written to disk.
        ///
        ///     Defaults to `true`.
        ///
        ///   - emitLMDBRepresentation: Whether or not an LMDB representation of the index should
        ///     written to disk.
        ///
        ///     Defaults to `true`.
        public func finalize(
            estimatedCount: Int? = nil,
            emitJSONRepresentation: Bool = true,
            emitLMDBRepresentation: Bool = true
        ) {
            precondition(!isCompleted, "Finalizing an already completed index build multiple times is not possible.")
            
            guard let navigatorIndex else {
                preconditionFailure("The navigatorIndex instance has not been initialized.")
            }
            
            let root = navigatorIndex.navigatorTree.root
            root.bundleIdentifier = bundleIdentifier

            let allReferences = pendingUncuratedReferences
            
            // Assign the children to the parents, starting with multi curated nodes
            var nodesMultiCurated = multiCurated.map { ($0, $1) }
            
            while !nodesMultiCurated.isEmpty {
                // The children of the multicurated nodes. These need to be tracked so we can multicurate them as well.
                var nodesMultiCuratedChildren: [(Identifier, NavigatorTree.Node)] = []
                
                for index in 0..<nodesMultiCurated.count {
                    let (nodeID, parent) = nodesMultiCurated[index]
                    let placeholders = identifierToChildren[nodeID]!
                    for reference in placeholders {
                        if let child = identifierToNode[reference] ?? externalNonSymbolNode(for: reference) {
                            parent.add(child: child)
                            pendingUncuratedReferences.remove(reference)
                            if !multiCurated.keys.contains(reference) && reference.fragment == nil {
                                // As the children of a multi-curated node is itself curated multiple times
                                // we need to process it as well, ignoring items with fragments as those are sections.
                                nodesMultiCuratedChildren.append((reference, child))
                                multiCurated[reference] = child
                            }
                        }
                    }
                    // Once assigned, placeholders can be removed as we use copy later.
                    identifierToChildren[nodeID]!.removeAll()
                }
                
                nodesMultiCurated = nodesMultiCuratedChildren
            }
                
            for (nodeIdentifier, placeholders) in identifierToChildren {
                for reference in placeholders {
                    let parent = identifierToNode[nodeIdentifier]!
                    if let child = identifierToNode[reference] ?? externalNonSymbolNode(for: reference) {
                        let needsCopy = multiCurated[reference] != nil
                        parent.add(child: (needsCopy) ? child.copy() : child)
                        pendingUncuratedReferences.remove(reference)
                    }
                }
            }
            
            var languageMaskToNode = [InterfaceLanguage.ID: NavigatorTree.Node]()
            if groupByLanguage {
                for language in navigatorIndex.availabilityIndex.interfaceLanguages {
                    let languageNode = NavigatorTree.Node(item: NavigatorItem(pageType: PageType.languageGroup.rawValue,
                                                                              languageID: language.mask,
                                                                              title: language.name,
                                                                              platformMask: Platform.Name.any.mask,
                                                                              availabilityID: UInt64(Self.availabilityIDWithNoAvailabilities)),
                                                          bundleIdentifier: bundleIdentifier)
                    languageMaskToNode[language.mask] = languageNode
                    root.add(child: languageNode)
                }
            }

            let curatedReferences = allReferences.subtracting(pendingUncuratedReferences)
            
            // The rest have no parent, so they need to be under the root.
            for nodeID in pendingUncuratedReferences {
                // Don't add symbol nodes to the root; if they have been dropped by automatic
                // curation, then they should not be in the navigator. In addition, treat unknown
                // page types as symbol nodes on the assumption that an unknown page type is a
                // symbol kind added in a future version of Swift-DocC.
                // Finally, don't add external references to the root; if they are not referenced within the navigation tree, they should be dropped altogether.
                if let node = identifierToNode[nodeID], PageType(rawValue: node.item.pageType)?.isSymbolKind == false, !node.item.isExternal {

                    // If an uncurated page has been curated in another language, don't add it to the top-level.
                    if curatedReferences.contains(where: { curatedNodeID in
                        curatedNodeID.isEquivalentIgnoringLanguage(to: nodeID)
                    }) {
                        continue
                    }

                    if groupByLanguage {
                        // Force unwrap is safe as we mapped this before
                        let languageNode = languageMaskToNode[node.item.languageID]!
                        languageNode.add(child: node)
                    } else {
                        root.add(child: node)
                    }
                }
            }
            
            // A list of items without curation, but still indexed.
            var fallouts = [NavigatorTree.Node]()

            if sortRootChildrenByName {
                root.children.sort(by: \.item.title)
                if groupByLanguage {
                    root.children.forEach { (languageGroup) in
                        languageGroup.children.sort(by: \.item.title)
                    }
                }
            }
            
            // If a set of supported languages is passed, merge the others.
            if groupByLanguage {
                if !fallouts.isEmpty {
                    fallouts.sort(by: { $0.item.title > $1.item.title })
                    let otherNode = NavigatorTree.Node(item: NavigatorItem(pageType: PageType.languageGroup.rawValue,
                                                                           languageID: InterfaceLanguage.undefined.mask,
                                                                           title: "Other",
                                                                           platformMask: Platform.Name.any.mask,
                                                                           availabilityID: UInt64(Self.availabilityIDWithNoAvailabilities),
                                                                           path: ""),
                                                                           bundleIdentifier: bundleIdentifier)
                    languageMaskToNode[InterfaceLanguage.any.mask] = otherNode
                    fallouts.forEach { (node) in
                        root.children.removeAll(where: { $0 == node})
                        node.children.forEach { otherNode.add(child: $0) }
                    }
                    root.add(child: otherNode)
                }
            }
            
            if emitJSONRepresentation {
                let renderIndex = RenderIndex.fromNavigatorIndex(navigatorIndex, with: self)
                
                let jsonEncoder = RenderJSONEncoder.makeEncoder(
                    prettyPrint: shouldPrettyPrintOutputJSON,
                    assetPrefixComponent: bundleIdentifier.split(separator: "/").joined(separator: "-")
                )
                jsonEncoder.outputFormatting.insert(.sortedKeys)
                
                let jsonNavigatorIndexURL = outputURL.appendingPathComponent("index.json")
                do {
                    let renderIndexData = try jsonEncoder.encode(renderIndex)
                    try renderIndexData.write(to: jsonNavigatorIndexURL)
                } catch {
                    self.problems.append(
                        error.problem(
                            source: nil,
                            severity: .error,
                            summaryPrefix: "Failed to write render index JSON to '\(jsonNavigatorIndexURL)': "
                        )
                    )
                }
                
            }
            
            guard emitLMDBRepresentation else {
                return
            }
            
            let environment: LMDB.Environment
            if let alreadyDefinedEnvironment = navigatorIndex.environment {
                environment = alreadyDefinedEnvironment
            } else {
                do {
                    environment = try LMDB.Environment(
                        path: navigatorIndex.url.path,
                        flags: [.noLock],
                        maxDBs: 4, mapSize: 100 * 1024 * 1024 // mapSize = 100MB
                    )
                    navigatorIndex.environment = environment
                } catch {
                    problems.append(
                        error.problem(
                            source: nil,
                            severity: .error,
                            summaryPrefix: "Failed to create navigator index LMDB environment: "
                        )
                    )
                    
                    return
                }
            }

            defer { environment.close() }

            let database: LMDB.Database
            if let alreadyDefinedDatabase = navigatorIndex.database {
                database = alreadyDefinedDatabase
            } else {
                do {
                    database = try environment.openDatabase(named: "index", flags: [.create])
                    navigatorIndex.database = database
                } catch {
                    problems.append(
                        error.problem(
                            source: nil,
                            severity: .error,
                            summaryPrefix: "Failed to create navigator index LMDB database: "
                        )
                    )
                    
                    return
                }
            }
            
            let information: LMDB.Database
            if let alreadyDefinedInformation = navigatorIndex.information {
                information = alreadyDefinedInformation
            } else {
                do {
                    information = try environment.openDatabase(named: "information", flags: [.create])
                    navigatorIndex.information = information
                } catch {
                    problems.append(
                        error.problem(
                            source: nil,
                            severity: .error,
                            summaryPrefix: "Failed to create navigator index LMDB information database: "
                        )
                    )
                    
                    return
                }
            }
            
            let availability: LMDB.Database
            if let alreadyDefinedAvailability = navigatorIndex.availability {
                availability = alreadyDefinedAvailability
            } else {
                do {
                    availability = try environment.openDatabase(named: "availability", flags: [.create])
                    navigatorIndex.availability = availability
                } catch {
                    problems.append(
                        error.problem(
                            source: nil,
                            severity: .error,
                            summaryPrefix: "Failed to navigator index LMDB availability database: "
                        )
                    )
                    
                    return
                }
            }
            
            do {
                for (newID, entryIDs) in availabilityIDs {
                    try availability.put(key: newID, value: entryIDs)
                }
            } catch {
                problems.append(
                    error.problem(
                        source: nil,
                        severity: .error,
                        summaryPrefix: "Failed to write navigator index availability information: "
                    )
                )
            }
            
            do {
                var records = [Record]()
                if let estimatedCount {
                    records.reserveCapacity(estimatedCount)
                }
                
                try navigatorIndex.navigatorTree.write(to: outputURL.appendingPathComponent("navigator.index"), writePaths: writePathsOnDisk) { node in
                    // Skip the nodes that have no content to present.
                    guard let pageType = PageType(rawValue: node.item.pageType) else { return }
                    guard !Set<PageType>([.root, .groupMarker, .languageGroup]).contains(pageType) else { return }
                    
                    // Retrieve the language, if possible.
                    guard let interfaceLanguage = self.navigatorIndex?.languageMaskToLanguage[node.item.languageID] else { return }
                    
                    // The fullPath needs to account for the language.
                    let fullPath = interfaceLanguage.name.lowercased() + node.item.path
                    
                    // Create the database records and store them in `records` for the time being.
                    records.append(
                        Record(
                            // Store the node to path mapping.
                            nodeMapping: (node.id!, fullPath),
                            // As we might have the same path curated in multiple places, we store only the first one found in the tree.
                            curationMapping: (navigatorIndex.pathHasher.hash(fullPath), node.id!),
                            // Store the USR to node relationship.
                            usrMapping: node.item.usrIdentifier.map({ ($0, node.id!) })
                        )
                    )
                }
                
                do {
                    // Write all records to disk in a single transaction.
                    try database.put(records: records)
                }
                // `put(records:)` throws only `LMDB.Database.NodeError.errorForPath`
                catch LMDB.Database.NodeError.errorForPath(let path, let error) {
                    if (error as? LMDB.Error) == LMDB.Error.keyExists {
                        self.problems.append(error.problem(source: self.outputURL,
                                                           severity: .information,
                                                           summaryPrefix: "Duplicated path found for \(path)"))
                    } else {
                        self.problems.append(error.problem(source: self.outputURL,
                                                           severity: .warning,
                                                           summaryPrefix: "The navigator index failed to map the data: \(error.localizedDescription)"))
                    }
                }

            } catch {
                problems.append(error.problem(source: outputURL,
                                              severity: .warning,
                                              summaryPrefix: "Couldn't write the navigator tree to the disk"))
            }
            
            // Write the availability index to the disk
            do {
                let plistEncoder = PropertyListEncoder()
                let encoded = try plistEncoder.encode(navigatorIndex.availabilityIndex)
                try encoded.write(to: outputURL.appendingPathComponent("availability.index"))
            } catch {
                problems.append(error.problem(source: outputURL,
                                              severity: .warning,
                                              summaryPrefix: "Couldn't write the availability index to the disk"))
            }
            
            // Insert the data about bundle identifier and items processed.
            do {
                let txn = environment.transaction()
                try txn.begin()
                try txn.put(key: NavigatorIndex.bundleKey, value: bundleIdentifier, in: information)
                try txn.put(key: NavigatorIndex.pathHasherKey, value: navigatorIndex.pathHasher.rawValue, in: information)
                try txn.put(key: NavigatorIndex.itemsIndexKey, value: counter, in: information)
                try txn.commit()
            } catch {
                problems.append(error.problem(source: outputURL,
                                              severity: .error,
                                              summaryPrefix: "LMDB failed to store the content"))
            }
                        
            var diagnostic = Diagnostic(source: outputURL,
                                             severity: .information,
                                             range: nil,
                                             identifier: "org.swift.docc.index",
                                             summary: "Indexed \(counter) entities")
            var problem = Problem(diagnostic: diagnostic, possibleSolutions: [])
            problems.append(problem)
            
            let availabilities = navigatorIndex.availabilityIndex.indexed
            diagnostic = Diagnostic(source: outputURL,
                                         severity: .information,
                                         range: nil,
                                         identifier: "org.swift.docc.index",
                                         summary: "Created index with \(availabilities)")
            problem = Problem(diagnostic: diagnostic, possibleSolutions: [])
            problems.append(problem)
            
            let treeString = root.dumpTree()
            diagnostic = Diagnostic(source: outputURL,
                                         severity: .information,
                                         range: nil,
                                         identifier: "org.swift.docc.index",
                                         summary: "Index tree:\n\(treeString)")
            problem = Problem(diagnostic: diagnostic, possibleSolutions: [])
            problems.append(problem)
        }

        /// Find an external node for the reference that is not of a symbol kind. The source language
        /// of the reference is ignored during this lookup since the reference assumes the target node
        /// to be of the same language as the page that it is curated in. This may or may not be true
        /// since non-symbol kinds (articles, tutorials, etc.) are not tied to a language.
        // This is a workaround for https://github.com/swiftlang/swift-docc/issues/240.
        // FIXME: This should ideally be solved by making the article language-agnostic rather
        // than accomodating the "Swift" language and special-casing for non-symbol nodes.
        func externalNonSymbolNode(for reference: NavigatorIndex.Identifier) -> NavigatorTree.Node? {
            identifierToNode
            .first { identifier, node in
                identifier.isEquivalentIgnoringLanguage(to: reference)
                && PageType.init(rawValue: node.item.pageType)?.isSymbolKind == false
                && node.item.isExternal
            }?.value
        }
        
        /// Build the index using the render nodes files in the provided documentation archive.
        /// - Returns: A list containing all the errors encountered during indexing.
        /// - Precondition: ``archiveURL`` is set.
        public func build() -> [Problem] {
            guard let archiveURL else {
                fatalError("Calling `build()` requires that `archiveURL` is set.")
            }
            
            setup()
            
            let dataDirectory = archiveURL.appendingPathComponent(NodeURLGenerator.Path.dataFolderName, isDirectory: true)
            for file in FileManager.default.recursiveFiles(startingPoint: dataDirectory) where file.pathExtension.lowercased() == "json" {
                do {
                    let data = try Data(contentsOf: file)
                    let renderNode = try RenderNode.decode(fromJSON: data)
                    try index(renderNode: renderNode)
                } catch {
                    problems.append(error.problem(source: file,
                                                  severity: .warning,
                                                  summaryPrefix: "RenderNode indexing process failed"))
                }
            }
            
            finalize()
            
            return problems
        }
        
        func availabilityEntryIDs(for availabilityID: UInt64) -> [Int]? {
            return availabilityIDs[Int(availabilityID)]
        }
    }
}

fileprivate extension Error {
    
    /// Returns a problem from an `Error`.
    func problem(source: URL?, severity: DiagnosticSeverity, summaryPrefix: String = "") -> Problem {
        let diagnostic = Diagnostic(source: source,
                                         severity: severity,
                                         range: nil,
                                         identifier: "org.swift.docc.index",
                                         summary: "\(summaryPrefix) \(localizedDescription)")
        return Problem(diagnostic: diagnostic, possibleSolutions: [])
    }
}


extension LMDB.Database {
    enum NodeError: Error {
        /// A database error that includes the path of a specific node and the original database error.
        case errorForPath(String, any Error)
    }
    
    /**
    Insert records into a database.
    
    - Parameters:
       - records: Key/value pairs to insert into the database.
       - flags: The list of `WriteFlags` to use for the put action.
    - Throws: An error in case a read-only transaction has been used, an invalid parameter has been specified, the database is full or the transaction has too many dirty pages to complete.
    > Warning: Wrap all thrown errors inside `NodeError` so the node path information is preserved.
    */
    func put(records: [NavigatorIndex.Builder.Record], flags: WriteFlags = []) throws {
        try LMDB.Transaction(environment: environment).run { database in
            try records.forEach { record in
                do {
                    try database.put(key: record.nodeMapping.0, value: record.nodeMapping.1, in: self, flags: flags)
                    try database.put(key: record.curationMapping.0, value: record.curationMapping.1, in: self, flags: flags)
                    if let usrMapping = record.usrMapping {
                        try database.put(key: usrMapping.0, value: usrMapping.1, in: self, flags: flags)
                    }
                } catch {
                    throw NodeError.errorForPath(record.nodeMapping.1, error)
                }
            }
        }
    }
}

/// A path hasher representation, used only internally in the navigator index to hash paths avoiding to persist long paths multiple times.
enum PathHasher: String {
    /// The `FNV-1` implementation.
    case fnv1 = "FNV-1"
    
    /// The `MD5` implementation, using the first 12 characters.
    case md5 = "MD5"
    
    /// Hashes a path using the selected strategy.
    func hash(_ value: String) -> String {
        switch self {
        case .fnv1: return value.stableHashString
        case .md5:
            let digest = Insecure.MD5.hash(data: Data(value.utf8)).map {
                String(format: "%02hhx", $0)
            }.joined().prefix(12)
            return String(digest)
        }
    }
}
